package com.le.high.class3;

import org.junit.Test;

import java.util.LinkedList;


/**
 * 给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右 括号，返回公式的计算结果。
 * 【举例】
 * str="48*((70-65)-43)+8*1"，
 * 返回-1816。 str="3+1*4"，
 * 返回7。 str="3+(1*4)"，返回7。
 * 【说明】
 * 1．可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
 * 2．如果是负数，就需要用括号括起来，比如"4*(-3)"。
 * 但如果负数作为公式的开头 或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)"都是合法的。
 * 3．不用考虑计算过程中会发生溢出的情况。
 */
public class Problem03_ExpressionCompute {


    public static int getValue(String str) {
        if (str == null || str.length() == 0) {
            return -1;
        }
        return value1(str.toCharArray(), 0)[0];

    }

    public static int[] value1(char[] chs, int i) {
        int num = 0;
        LinkedList<String> que = new LinkedList<>();
        int[] res = null;
        while (i < chs.length && chs[i] != ')') {
            if (chs[i] >= 48 && chs[i] <= 57) {
                num = num * 10 + (chs[i++] - '0');
            } else if (chs[i] != '(') {
                addNum(que, num);
                que.offerLast(String.valueOf(chs[i++]));
                num = 0;
            } else {
                // 左括号
                res = value1(chs, i + 1);
                num = res[0];
                i = res[1] + 1;
            }
        }
        addNum(que, num);
        return new int[]{getNum(que), i};

    }

    // 队列中只保留 数字 + -
    public static void addNum(LinkedList<String> que, int num) {
        if (!que.isEmpty()) {
            int cur = 0;
            String top = que.pollLast();
            if (top.equals("+") || top.equals("-")) {
                que.offerLast(top);
            } else {
                // * /
                cur = Integer.parseInt(que.pollLast());
                num = top.equals("*") ? (cur * num) : (cur / num);
            }
        }
        que.offerLast(String.valueOf(num));
    }

    // 统计队列累加和，从左->右  右->左都可
    public static int getNum(LinkedList<String> que) {
        boolean isAdd = true;
        int num = 0;
        String cur = null;
        int sum = 0;
        while (!que.isEmpty()) {
            cur = que.pollFirst();
            if (cur.equals("+")) {
                isAdd = true;
            } else if (cur.equals("-")) {
                isAdd = false;
            } else {
                num = Integer.parseInt(cur);
                sum += isAdd ? num : -num;
            }
        }
        return sum;
    }

    @Test
    public void test() {
        String exp = "-3*4";
        System.out.println((getValue(exp)));

        exp = "4*(6+78)+53-9/2+45*8";
        System.out.println(getValue(exp));

        exp = "10-5*3";
        System.out.println(getValue(exp));


        exp = "3+1*4";
        System.out.println(getValue(exp));
    }
}
